//区间dp,f[i][j]=min{f[i][k]+f[k][j]+v[i]*v[j]*v[k]}
//f[i][j]=0,j-i<2
import java.util.Arrays;

public class Solution1039 {

    int[][] f=new int[60][60];

    public int minScoreTriangulation(int[] values) {
        for (int i=0;i<60;i++){
            Arrays.fill(f[i],-1);
        }
        return dfs(values,f,0,values.length-1);
    }

    private int dfs(int[] values, int[][] f, int l, int r) {
        if (r-l<2){
            return 0;
        }else if (r-l==2){
            return values[r]*values[l]*values[l+1];
        }else {
            if (f[l][r]==-1){
                int min=Integer.MAX_VALUE;
                for (int i=l+1;i<r;i++){
                    min=Math.min(min,dfs(values,f,l,i)+dfs(values,f,i,r)+values[l]*values[r]*values[i]);
                }
                f[l][r]=min;
            }
            return f[l][r];
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution1039().minScoreTriangulation(new int[]{1,3,1,4,1,5}));
    }
}
